1. Field of the Invention
The present invention relates to communication network apparatus such as is used to link information handling systems or computers of various types and capabilities and to components and methods for data processing in such an apparatus. More particular the present invention relates to schedulers used in such devices to indicate when the next packet is to be transmitted from queues within the devices.
2. Description of the Prior Art
Scheduling the transmission of packets between points within a communications device or between points in the communications device and an external transmission network is well known in the prior art. The conventional approach is to provide a plurality of queues within the device and packets to be transmitted are enqueued to selected queues. A timing device sometimes called a timing wheel or calendar is searched to determine when the next packet is to be dequeued and forwarded from the queues. The selection, queueing and dequeueing of packets are controlled by several factors collectively referred to as Quality of Service (QoS). Because the factors and QoS requirements are well known in the prior art further discussion is not warranted. Suffice it to say U.S. Pat. Nos. 5,533,020 and 6,028,843 are examples of prior art.
Even though the prior art devices work well for their intended purposes and in the case of U.S. Pat. Nos. 5,533,020 and 6,028,843 the technology has been advanced beyond what it was at the time when these patents were invented, the communications technology is faced with new problems requiring new techniques and solutions.
One of the problems is that the volume of data has increased due to the increase in the number of users. There are also demands to improve QoS. To address these problems it is desirable to use a hardware scheduler to schedule the transmission of packets from queues in the network devices. It is common knowledge that the hardware implementation of a device or function is usually faster than its corresponding software implementation. On the other hand it is easier to change the software implementation of a device or function than it is to change the hardware implementation.
Notwithstanding, the hardware implementation of a scheduler presents certain problems which have to be addressed if the scheduler is to be used in an environment in which QoS and packet throughput are relatively high. Among the problems to overcome are:                (1) a physical limitation as to how much “searching” can be done in one of the system clock cycles, as each circuit in the hardware implementation consumes a finite amount of time against the clock period.        (2) a finite number of clock cycles that the search must be completed by, as the winning calendar location (discussed below) must be used by the Scheduler circuits downstream as a part of the overall Scheduler function. So, reducing the number of clock cycles it takes to find a winner is very important.        (3) a need to change the number of entries in the timing wheel for the search to meet customer demands, as new generations of Hardware Scheduler or related functions emerge.        (4) changing system clock frequencies.        (5) changing hardware technologies.        
The scheduler and in particular the time share calendar search described below overcomes these problems and can be easily redesigned to meet new requirements due to change in technology, increase in the amount of packets to be handled, etc.